package graph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * 拓扑排序，如何获取写项目的时候的第三方库的编译顺序，项目依赖是一个无环图结构
 *
 * @author Liaorun
 */
public class TopologySort {

    public static List<Node> sortedTopology(Graph graph) {
        // key: 某一个点 value: 剩余的入度
        HashMap<Node, Integer> inMap = new HashMap<>();

        // 入度为0的点，才能进入这个队列
        // 为什么不把入度为0的点当成最终结果？ 答：可能存在多个入度为0的点，还需要遍历处理一次
        LinkedList<Node> zeroInQueue = new LinkedList<>();

        // 将图中所有的点和入度获取记录
        for (Node node : graph.nodes.values()) {
            inMap.put(node, node.in);

            if (node.in == 0) {
                // 入度为0单独记录，无环图结构肯定有入度为0的
                // 必须一开始全部找出来，如果只找一个，
                // 后面这些其他一开始就入度为0的点就不能记录到结果队列
                zeroInQueue.add(node);
            }
        }
        // 拓扑排序的结果，依此加入result
        ArrayList<Node> result = new ArrayList<>();

        while (!zeroInQueue.isEmpty()) {

            // 选一个入度为0的为当前节点，放到结果队列
            Node cur = zeroInQueue.poll();
            result.add(cur);

            // 处理当前节点出度连接的点
            for (Node next : cur.nexts) {
                // 将这些点的入度 - 1
                inMap.put(next, inMap.get(next) - 1);
                if (inMap.get(next) == 0) {
                    // 减完后放到队列中记录
                    zeroInQueue.add(next);
                }
            }
        }

        return result;
    }
}
